package 贪心算法;

public class 加油站 {
    class Solution{
        public int canCompleteCircuit(int[] gas,int[] cost){
           int currSum = 0;
           int totalSum = 0;
           int index = 0;
            for (int i = 0; i < gas.length; i++) {
                currSum += gas[i] - cost[i];
                totalSum+= gas[i] - cost[i];
                if (currSum<0){
                    //第i个加油站肯定是不够油的了，只有下一个 若下一个还是没油够就再继续
                    index = (i+1) % gas.length;
                    currSum = 0;
                }
            }

            if (totalSum<0) return -1;
            return index;
        }
    }
}
